package sort;

/**
 * @Author: Yangu
 * @Created time: 2021/1/9 16:35
 * @Description :
 */
public class InsertSort {

    /**
     * 插入排序，分解为前面是有序数组，后面是无序数组，将后面的数据插入前面数据的适当位置
     * @param arr
     * @return
     */
    public static Integer[] sort(Integer [] arr) {
        int out,in;
        //从第二个开始比
        for(out=1; out< arr.length; out++) {
            int temp = arr[out];
            in = out;
            //比到in=1的时候结束
            while(in > 0 && arr[in-1] >= temp) {
                arr[in] = arr[in -1];
                --in;
            }
            //将其插入空缺位，插入排序
            arr[in] = temp;
        }
        return arr;
    }
}
